package com.sheng.leetcode.year2022.month06.day16;

import org.junit.Test;

import java.util.HashMap;

/**
 * @author liusheng
 * @date 2022/06/16
 *
 * 532. 数组中的 k-diff 数对
 *
 * 给定一个整数数组和一个整数 k，你需要在数组里找到 不同的 k-diff 数对，并返回不同的 k-diff 数对 的数目。
 * 这里将 k-diff 数对定义为一个整数对 (nums[i], nums[j])，并满足下述全部条件：
 * 0 <= i < j < nums.length
 * |nums[i] - nums[j]| == k
 * 注意，|val| 表示 val 的绝对值。
 *
 * 示例 1：
 *
 * 输入：nums = [3, 1, 4, 1, 5], k = 2
 * 输出：2
 * 解释：数组中有两个 2-diff 数对, (1, 3) 和 (3, 5)。
 * 尽管数组中有两个1，但我们只应返回不同的数对的数量。
 * 示例 2：
 *
 * 输入：nums = [1, 2, 3, 4, 5], k = 1
 * 输出：4
 * 解释：数组中有四个 1-diff 数对, (1, 2), (2, 3), (3, 4) 和 (4, 5)。
 * 示例 3：
 *
 * 输入：nums = [1, 3, 1, 5, 4], k = 0
 * 输出：1
 * 解释：数组中只有一个 0-diff 数对，(1, 1)。
 *
 * 提示：
 *
 * 1 <= nums.length <= 104
 * -107 <= nums[i] <= 107
 * 0 <= k <= 107
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/k-diff-pairs-in-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0532 {

    @Test
    public void test01(){
//        int[] nums = {3, 1, 4, 1, 5};
//        int k = 2;
//        int[] nums = {1, 2, 3, 4, 5};
//        int k = 1;
//        int[] nums = {1, 3, 1, 5, 4};
//        int k = 0;
        //2
//        int[] nums = {1,2,4,4,3,3,0,9,2,3};
//        int k = 3;
        //3
        int[] nums = {6,2,9,3,9,6,7,7,6,4};
        int k = 3;
        System.out.println(new Solution().findPairs(nums, k));
    }

}
class Solution {
    public int findPairs(int[] nums, int k) {
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        //会导致key覆盖，不可取
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                if (!(map.containsKey(nums[i]) && (map.get(nums[i]) == nums[j]))
//                        && !(map.containsKey(nums[j]) && (map.get(nums[j]) == nums[i]))) {
//                    if (Math.abs(nums[i] - nums[j]) == k) {
//                        count++;
//                        map.put(nums[i], nums[j]);
//                    }
//                }
//            }
//        }
        for (int num : nums) {
            //以数组值为key，数组值的出现次数为value
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        for (Integer integer : map.keySet()) {
            if (k == 0) {
                //k为0时，即为相同值相减才能等于k，所以计算map中value大于1的个数即可
                if (map.get(integer) > 1) {
                    count++;
                }
            } else {
                //绝对值不分先后顺序，如果存在key为当前值加上k，则代表相减一定为k
                if (map.containsKey(integer + k)) {
                    count++;
                }
            }
        }
        return count;
    }
}

//相似解答
//class Solution {
//    public int findPairs(int[] nums, int k) {
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
//        int ans = 0;
//        for (int i : nums) {
//            if (map.get(i) == 0) continue;
//            if (k == 0) {
//                if (map.get(i) > 1) ans++;
//            } else {
//                int a = i - k, b = i + k;
//                if (map.getOrDefault(a, 0) > 0) ans++;
//                if (map.getOrDefault(b, 0) > 0) ans++;
//            }
//            map.put(i, 0);
//        }
//        return ans;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/k-diff-pairs-in-an-array/solution/by-ac_oier-ap3v/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
